class Solution {
public:
    int trap(vector<int>& height) {
        if(height.empty())
            return 0;
        int res = 0;
        vector<int> dp_max_left(height.size());
        vector<int> dp_max_right(height.size());
        dp_max_left[0] = height[0];
        dp_max_right[height.size()-1] = height[height.size()-1];
        for(int i = 1; i < height.size(); i++)
        {
            dp_max_left[i] = max(dp_max_left[i-1], height[i]);
        }
        for(int i = height.size()-2; i >= 0; i--)
        {
            dp_max_right[i] = max(dp_max_right[i+1], height[i]);
        }
        for(int i = 1; i < height.size(); i++)
        {
            res = min(dp_max_left[i], dp_max_right[i]) - height[i] + res;
        }
        return res;
    }
};

class Solution {
public:
    int trap(vector<int>& height) {

        int res = 0;

        for(int i = 1; i < height.size(); i++)
        {
            int max_left = 0;
            int max_right = 0;
            for(int j = i; j >= 0; j--)
                max_left = max(max_left, height[j]);
            for(int j = i; j < height.size(); j++)
                max_right = max(max_right, height[j]);
            res = min(max_left, max_right) - height[i] + res;
        }

        return res;
    }
};